package double_pointer;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description 剑指 Offer 57 - II. 和为s的连续正数序列
 * k神题解中给了一个数学的求法,那个有点麻烦,难想到,我还是用滑动窗口
 * @Author Firenut
 * @Date 2023-01-26 22:41
 */
public class T57_II_findContinuousSequence {
    @Test
    public void test() {
        findContinuousSequence1(9);
    }

    // 使用滑动窗口
    public int[][] findContinuousSequence2(int target) {
        int i = 1, j = 2;
        List<int[]> res=new ArrayList<>();
        int sign = i + j;
        while (i < j) {
            if (sign < target) {
                j++;
                sign += j;
            } else if (sign == target) { //记录结果
                int[] array = new int[j - i + 1];
                for (int k = i; k <= j; k++) {
                    array[k - i] = k;
                }
                res.add(array);
                j++;    //移动左指针也可以
                sign += j;
            } else {
                sign -= i;
                i++;

            }
        }

//        return res.toArray(new int[res.size()][]);
        return res.toArray(new int[0][]); // new int[0][] 动态创建和集合res相同容量的数组,性能是最好的(比起new int[res.size()][])
        // 如果是一维的,就使用 res.toArray(new int[0])
    }


    // 此解法没用用到滑动窗口,效率很低，而且没有剪枝,没有利用到有序数组这个隐藏条件
    public int[][] findContinuousSequence1(int target) {
        int i=1,j=2,end=target/2+1;
        List<int[]> res=new ArrayList<>();
        int ans;
        while(i<=end){
            ans=i;
            for(j=i+1;j<=end;j++){
                if(ans+j<target){
                    ans+=j;
                }else if(ans+j==target){
                    int []array=new int[j-i+1];
                    int k=i;
                    int r=0;
                    while(k<=j){
                        array[r++]=k++;
                    }
                    res.add(array);
                }else{
                    break;
                }
            }
            i++;
        }
        return res.toArray(new int[0][]); // 转成二维数组
    }
}
